31. 下一个排列

为保证权益，题目请参考 31. 下一个排列(From LeetCode).

解决方案1

CPP

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    static void nextPermutation(vector<int> &nums) {

        // 找到可以进行更改的下标
        int index=-1;
        for (int i = nums.size() - 1; i >= 1; i--) {
            if (nums[i - 1] < nums[i]) {
                index = i - 1;
//                restart = false;
                break;
            }
        }

        // 替换
        if(index != -1){
            for (int i = nums.size() - 1; i >= 1; i--) {
                if (nums[index] < nums[i]) {
                    int t = nums[index];
                    nums[index] = nums[i];
                    nums[i] = t;
                    break;
                }
            }
        }

        // 排序（冒泡）
        for (int i = index + 1; i < nums.size(); i++) {
            for (int j = nums.size() - 1; j > index + 1; j--) {
                if (nums[j - 1] > nums[j]) {
                    int t = nums[j - 1];
                    nums[j - 1] = nums[j];
                    nums[j] = t;
                }
            }
        }
    }
};

int main() {
    vector<int> nums;
    nums.push_back(1);
    nums.push_back(3);
    nums.push_back(2);

    Solution so;
    so.nextPermutation(nums);

    for(auto x:nums){
        cout << x << endl;
    }
    return 0;
}

Python

# 31. 下一个排列
# https://leetcode-cn.com/problems/next-permutation/
from typing import List


class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l = -1
        r = len(nums)
        for j in range(len(nums) - 1, -1, -1):
            if j > 0 and nums[j - 1] < nums[j]:
                l = j - 1
                break
        if l == -1:
            nums.sort()
            return

        for j in range(len(nums) - 1, -1, -1):
            if nums[j] > nums[l]:
                r = j
                break

        nums[l], nums[r] = nums[r], nums[l]

        for i in range(l + 1, len(nums) - 1):
            t = len(nums) - 1 - (i - (l + 1))
            if i < t:
                nums[i], nums[t] = nums[t], nums[i]
            else:
                break


if __name__ == "__main__":
    solution = Solution()
    t = [3, 2, 1]
    solution.nextPermutation(t)
    print(t)